package data_structur.SparseArray;

/**
 * 稀疏数组：大部分值为0
 */
public class SparseArray {

    private void test1(){
        // 创建原始二维数组
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[4][5] = 2;
        System.out.println("原始二维数组:");
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.print(data+"\t");
            }
            System.out.println();
        }

        // 得到有效值个数
        int sum = 0;
        for (int i = 0; i < 11; i++){
            for (int j = 0; j < 11 ; j++){
                if (chessArr[i][j] != 0){
                    sum++;
                }
            }
        }
        System.out.println("有效值个数：" + sum);
        System.out.println();

        // 将二位数组转化为稀疏数组
        System.out.println("二位数组转稀疏数组：");
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        sum = 0;
        for (int i = 0; i < 11; i++){
            for (int j = 0; j < 11 ; j++){
                if (chessArr[i][j] != 0){
                    sum += 1;
                    sparseArr[sum][0] = i;
                    sparseArr[sum][1] = j;
                    sparseArr[sum][2] = chessArr[i][j];
                }
            }
        }
        System.out.println("row\tcol\tdata");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        System.out.println();

        // 将稀疏数组转换为二维数组
        System.out.println("稀疏数组转二维数组：");
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int row = 1 ; row <= sparseArr[0][2] ; row++){
            chessArr2[sparseArr[row][0]][sparseArr[row][1]] = sparseArr[row][2];
        }
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }

    }

    public static void main(String[] args) {
        SparseArray sparseArray = new SparseArray();
        sparseArray.test1();
    }

}
